/*************************************************
* 5、编写一个算法，计算矩阵A(mXn) 的鞍点。
* 如元素aij是第i行的最小元素同时又是第j列的最大元素，
* 则称为A的鞍点。如不存在，则返回0值
*************************************************/

#include<stdio.h>
#include<malloc.h>
#define INF 2147483647

typedef struct {int col,row,data;} triple;
typedef struct{int col,row;int* data;} mat;

void print_mat(const mat* m){
    int i,j;
    printf("<Matrix %dx%d>\n",m->row,m->col);
    for(i=0;i<m->col;i++){
        for(j=0;j<m->row;j++)printf("%d\t",(m->data)[i*m->col+j]);
        putchar('\n');
    }
}

void display_sparse_mat_table(const triple* m){
    printf("<SparseMatrix %dx%d with %d element%s>\n",m->row,m->col,m->data,m->data>1?"s":"");
    if(m->data)printf(" row| col|data\n");
    for(int i=1;i<=m->data;i++)
        printf("%4d|%4d|%4d\n",m[i].row,m[i].col,m[i].data);
}


// returns an array of tuples
// first element is (row,col,num_of_saddle_points)
triple* mat_saddle(mat* m){
    triple* t = malloc(sizeof(triple)*(m->row+1));
    t->data = m->row; t->row = m->row; t->col = 1;
    int i,j,k,l;
    for(i=0;i<m->row;i++){
        k = INF; l = -1;
        for(j=0;j<m->col;j++)
            if(m->data[i*m->col+j] < k) {k = m->data[i*m->col+j]; l = j;}
        t[i+1].data = k;
        t[i+1].col = l+1;
        t[i+1].row = i+1;
    }
    k = 0;
    for(i=0;i<t->data;i++){
        for(j=0;j< m->row;j++){
            if(m->data[j * m->row + t[i+1].col-1] > t[i+1].data ){ t[i+1].row = 0;k++;break;}
        }
    }
    triple* res = malloc(sizeof(triple)*(t->data + 1 - k));
    res->data = t->data  - k; res->row = m->row; res->col = m->col;
    for(i=j=0;i<t->data;i++){
        if(t[i+1].row){
            res[++j].data = t[i+1].data;
            res[j].col = t[i+1].col;
            res[j].row = t[i+1].row;
        }
    }
    free(t);
    return res;
}



int main(){
    int i,j;
    printf("Enter matrix size row x col :");
    scanf("%d%d",&i,&j);
    printf("Enter Matrix by rows:\n");
    mat A; A.row = i; A.col = j;
    A.data = malloc(sizeof(int)*A.row*A.col);
    for(i =0;i<A.row;i++){
        printf("Row #%d> ",i+1);
        for(j=0;j<A.col;j++){scanf("%d",A.data+i*A.col+j);}fflush(stdin);
    }
    print_mat(&A);
    triple* t = mat_saddle(&A);
    display_sparse_mat_table(t);

    free(A.data);
    free(t);
    return 0;
}